<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Exercises
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial089.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial086.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc177">12.4</A>&nbsp;&nbsp;Exercises</H2>

For exercises 1-3, start from the constraint model for the queens problem
given in section <A HREF="tutorial088.html#queenscode">12.2.4</A>. It is available in the examples directory
as queens_ic.ecl.
<OL CLASS="enumerate" type=1><LI CLASS="li-enumerate">Use the search/6 predicate from the ic_search library and the
standard model for the queens problem (given below) to find ONE
solution to the 42-queens problem.
With a naive search strategy this requires millions of backtracks.
Using heuristics and/or incomplete search, try to find a solution
in less than 100 backtracks!<BR>
<BR>
<LI CLASS="li-enumerate">How many solutions does the 9-queens problem have?<BR>
<BR>
<LI CLASS="li-enumerate">Solve the "8 sticky queens problem": Assume that the queens
in neighbouring columns want to stick together as close as possible.
Minimize the sum of the vertical distances between neighbouring queens.
What is the best and what is the worst solution for this problem?<BR>
<BR>
<LI CLASS="li-enumerate">For given N, create a list of length N whose members are numbers
between 1 and N (inclusive), which are all different (easy so far) 
and satisfy the following constraint.
For each element E of the list, its successors are divided into two sets,
 <UL CLASS="itemize"><LI CLASS="li-itemize">
 BiggerE: the successors which are greater than E and
 <LI CLASS="li-itemize">SmallerE: the successors less than E.
 </UL>
(Thus no successor takes the same value as E).
The cardinalities of the sets BiggerE and SmallerE differ by at most 1. <BR>
<BR>
<LI CLASS="li-enumerate">A harder version of the problem is similar.
For given N, create a list of length N whose members are numbers
between 1 and some upper bound Max (start with, say Max = <I>N</I><SUP>2</SUP>), 
which are all different (easy so far) 
and satisfy the following (more complex) constraint.
For each K from 1..N, call the Kth element of the list Ek. 
Its successors are divided into two sets, as before:
 <UL CLASS="itemize"><LI CLASS="li-itemize">
 BiggerEk: the successors which are greater than or equal to Ek + K and
 <LI CLASS="li-itemize">SmallerEk: the successors less than or equal to Ek - K.
 </UL>
(Thus no successor takes a value between Ek-K+1 and Ek+K-1.)
The cardinalities of the sets BiggerEk and SmallerEk differ 
by at most 1. <BR>
<BR>
What is the smallest upper bound Max for which there is a feasible solution?</OL>
<HR>
<A HREF="tutorial089.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial086.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
</BODY>
</HTML>
